{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #快速公交"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: busRapidTransit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #快速公交"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣打算去秋日市集，由于游客较多，小扣的移动速度受到了人流影响：\r\n",
    "- 小扣从 `x` 号站点移动至 `x + 1` 号站点需要花费的时间为 `inc`；\r\n",
    "- 小扣从 `x` 号站点移动至 `x - 1` 号站点需要花费的时间为 `dec`。\r\n",
    "\r\n",
    "现有 `m` 辆公交车，编号为 `0` 到 `m-1`。小扣也可以通过搭乘编号为 `i` 的公交车，从 `x` 号站点移动至 `jump[i]*x` 号站点，耗时仅为 `cost[i]`。小扣可以搭乘任意编号的公交车且搭乘公交次数不限。\r\n",
    "\r\n",
    "假定小扣起始站点记作 `0`，秋日市集站点记作 `target`，请返回小扣抵达秋日市集最少需要花费多少时间。由于数字较大，最终答案需要对 1000000007 (1e9 + 7) 取模。\r\n",
    "\r\n",
    "注意：小扣可在移动过程中到达编号大于 `target` 的站点。\r\n",
    "\r\n",
    "**示例 1：**\r\n",
    ">输入：`target = 31, inc =  5, dec = 3, jump = [6], cost = [10]`\r\n",
    ">\r\n",
    ">输出：`33`\r\n",
    ">\r\n",
    ">解释：\r\n",
    ">小扣步行至 1 号站点，花费时间为 5；\r\n",
    ">小扣从 1 号站台搭乘 0 号公交至 6 * 1 = 6 站台，花费时间为 10；\r\n",
    ">小扣从 6 号站台步行至 5 号站台，花费时间为 3；\r\n",
    ">小扣从 5 号站台搭乘 0 号公交至 6 * 5 = 30 站台，花费时间为 10；\r\n",
    ">小扣从 30 号站台步行至 31 号站台，花费时间为 5；\r\n",
    ">最终小扣花费总时间为 33。\r\n",
    "\r\n",
    "\r\n",
    "**示例 2：**\r\n",
    ">输入：`target = 612, inc =  4, dec = 5, jump = [3,6,8,11,5,10,4], cost = [4,7,6,3,7,6,4]`\r\n",
    ">\r\n",
    ">输出：`26`\r\n",
    ">\r\n",
    ">解释：\r\n",
    ">小扣步行至 1 号站点，花费时间为 4；\r\n",
    ">小扣从 1 号站台搭乘 0 号公交至 3 * 1 = 3 站台，花费时间为 4；\r\n",
    ">小扣从 3 号站台搭乘 3 号公交至 11 * 3 = 33 站台，花费时间为 3；\r\n",
    ">小扣从 33 号站台步行至 34 站台，花费时间为 4；\r\n",
    ">小扣从 34 号站台搭乘 0 号公交至 3 * 34 = 102 站台，花费时间为 4；\r\n",
    ">小扣从 102 号站台搭乘 1 号公交至 6 * 102 = 612 站台，花费时间为 7； \r\n",
    ">最终小扣花费总时间为 26。\r\n",
    "\r\n",
    "\r\n",
    "**提示：**\r\n",
    "- `1 <= target <= 10^9`\r\n",
    "- `1 <= jump.length, cost.length <= 10`\r\n",
    "- `2 <= jump[i] <= 10^6`\r\n",
    "- `1 <= inc, dec, cost[i] <= 10^6`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [meChtZ](https://leetcode.cn/problems/meChtZ/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [meChtZ](https://leetcode.cn/problems/meChtZ/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['31\\n5\\n3\\n[6]\\n[10]', '612\\n4\\n5\\n[3,6,8,11,5,10,4]\\n[4,7,6,3,7,6,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def busRapidTransit(self, target, inc, dec, jump, cost):\n",
    "        \"\"\"\n",
    "        :type target: int\n",
    "        :type inc: int\n",
    "        :type dec: int\n",
    "        :type jump: List[int]\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #自底向上记忆化递推   \n",
    "        memo = dict() #记忆字典\n",
    "        def findroute(cur_target):  \n",
    "            if cur_target==0:     #当前站点已经是0了返回0代价\n",
    "                return 0\n",
    "            if cur_target in memo:\n",
    "                return memo[cur_target]\n",
    "            mincost = cur_target*inc  #最小代价初始化为直接回终点站，我相信这种情况应该存在\n",
    "\n",
    "            for i,val in enumerate(jump): #遍历附近的公交站点\n",
    "                if cur_target>1:#至少得大于1，不然我自己走了还坐个屁公交\n",
    "                    if cur_target%val==0: #当前站能够坐公交\n",
    "                        mincost =min(mincost,cost[i]+findroute(cur_target//val)) #递归下一站\n",
    "                    else:\n",
    "                        bias = cur_target%val #当前站不能做公交看看需要走几步到达公交站  \n",
    "                        if cur_target-bias>0: #往前走几步如果没到终点，就该坐公交，递归下一站\n",
    "                            mincost=min(mincost,bias*inc+cost[i]+findroute(cur_target//val))\n",
    "\n",
    "                        mincost = min(mincost,(val-bias)*dec+cost[i]+findroute(cur_target//val+1))#往后走几步坐公交递归下一站\n",
    "            memo[cur_target]=mincost\n",
    "            return mincost\n",
    "\n",
    "        return findroute(target)%(1000000007)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "\n",
    "        cache = {0:0, 1:inc}\n",
    "\n",
    "        def helper(pos: int) -> int:\n",
    "            if pos in cache:\n",
    "                return cache[pos]\n",
    "\n",
    "            min_dis = inc * pos\n",
    "            for i in range(len(jump)):\n",
    "                j = jump[i]\n",
    "                c = cost[i]\n",
    "\n",
    "                bias = pos % j\n",
    "\n",
    "                if bias == 0:\n",
    "                    min_dis = min(min_dis, c + helper(pos//j))\n",
    "                \n",
    "                else:\n",
    "                    if pos > j:\n",
    "                        min_dis = min(min_dis, inc*bias + c + helper(pos//j))\n",
    "                    else:\n",
    "                        min_dis = min(min_dis, inc*bias + helper(pos//j))\n",
    "                \n",
    "                    min_dis = min(min_dis, dec*(j-bias) + c + helper(pos//j+1))\n",
    "\n",
    "            cache[pos] = min_dis\n",
    "\n",
    "            return min_dis \n",
    "\n",
    "        return helper(target)% (10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        memo = dict() #记忆字典\n",
    "        def findroute(cur_target):  \n",
    "            if cur_target==0:     #当前站点已经是0了返回0代价\n",
    "                return 0\n",
    "            if cur_target in memo:\n",
    "                return memo[cur_target]\n",
    "            mincost = cur_target*inc  #最小代价初始化为直接回终点站，我相信这种情况应该存在\n",
    "\n",
    "            for i,val in enumerate(jump): #遍历附近的公交站点\n",
    "                if cur_target>1:#至少得大于1，不然我自己走了还坐个屁公交\n",
    "                    if cur_target%val==0: #当前站能够坐公交\n",
    "                        mincost =min(mincost,cost[i]+findroute(cur_target//val)) #递归下一站\n",
    "                    else:\n",
    "                        bias = cur_target%val #当前站不能做公交看看需要走几步到达公交站  \n",
    "                        if cur_target-bias>0: #往前走几步如果没到终点，就该坐公交，递归下一站\n",
    "                            mincost=min(mincost,bias*inc+cost[i]+findroute(cur_target//val))\n",
    "\n",
    "                        mincost = min(mincost,(val-bias)*dec+cost[i]+findroute(cur_target//val+1))#往后走几步坐公交递归下一站\n",
    "            memo[cur_target]=mincost\n",
    "            return mincost\n",
    "\n",
    "        return findroute(target)%(1000000007)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(x) -> int:\n",
    "            if x == 0:\n",
    "                return 0\n",
    "            if x == 1:\n",
    "                return inc\n",
    "            res = x * inc\n",
    "            for i,jmp in enumerate(jump):\n",
    "                res = min(res,inc * (x % jmp) + cost[i] + dfs(x // jmp))\n",
    "                if x % jmp != 0:\n",
    "                    res = min(res,dec * (jmp - x % jmp) + cost[i] + dfs(x // jmp + 1))\n",
    "            return res\n",
    "        return dfs(target) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def busRapidTransit(self, target, inc, dec, jump, cost):\n",
    "        \"\"\"\n",
    "        :type target: int\n",
    "        :type inc: int\n",
    "        :type dec: int\n",
    "        :type jump: List[int]\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #自底向上记忆化递推   \n",
    "        memo = dict() #记忆字典\n",
    "        def findroute(cur_target):  \n",
    "            if cur_target==0:     #当前站点已经是0了返回0代价\n",
    "                return 0\n",
    "            if cur_target in memo:\n",
    "                return memo[cur_target]\n",
    "            mincost = cur_target*inc  #最小代价初始化为直接回终点站，我相信这种情况应该存在\n",
    "\n",
    "            for i,val in enumerate(jump): #遍历附近的公交站点\n",
    "                if cur_target>1:#至少得大于1，不然我自己走了还坐个屁公交\n",
    "                    if cur_target%val==0: #当前站能够坐公交\n",
    "                        mincost =min(mincost,cost[i]+findroute(cur_target//val)) #递归下一站\n",
    "                    else:\n",
    "                        bias = cur_target%val #当前站不能做公交看看需要走几步到达公交站  \n",
    "                        if cur_target-bias>0: #往前走几步如果没到终点，就该坐公交，递归下一站\n",
    "                            mincost=min(mincost,bias*inc+cost[i]+findroute(cur_target//val))\n",
    "\n",
    "                        mincost = min(mincost,(val-bias)*dec+cost[i]+findroute(cur_target//val+1))#往后走几步坐公交递归下一站\n",
    "            memo[cur_target]=mincost\n",
    "            return mincost\n",
    "\n",
    "        return findroute(target)%(1000000007)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        #自底向上记忆化递推   \n",
    "        memo = dict() #记忆字典\n",
    "        \n",
    "        def findroute(cur_target: int) -> int:  \n",
    "            if cur_target == 0:     #当前站点已经是0了返回0代价\n",
    "                return 0\n",
    "            if cur_target in memo:\n",
    "                return memo[cur_target]\n",
    "            mincost = cur_target*inc  #最小代价初始化为直接回终点站，我相信这种情况应该存在\n",
    "\n",
    "            for i,val in enumerate(jump): #遍历附近的公交站点\n",
    "                if cur_target>1:#至少得大于1，不然我自己走了还坐个屁公交\n",
    "                    if cur_target%val==0: #当前站能够坐公交\n",
    "                        mincost =min(mincost,cost[i]+findroute(cur_target//val)) #递归下一站\n",
    "                    else:\n",
    "                        bias = cur_target%val #当前站不能做公交看看需要走几步到达公交站  \n",
    "                        if cur_target-bias>0: #往前走几步如果没到终点，就该坐公交，递归下一站\n",
    "                            mincost=min(mincost,bias*inc+cost[i]+findroute(cur_target//val))\n",
    "\n",
    "                        mincost = min(mincost,(val-bias)*dec+cost[i]+findroute(cur_target//val+1))#往后走几步坐公交递归下一站\n",
    "            memo[cur_target]=mincost\n",
    "            return mincost\n",
    "\n",
    "        return findroute(target)%(1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "            \n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(length):\n",
    "            if length == 0:\n",
    "                return 0\n",
    "            ans = length * inc\n",
    "            for j, c in zip(jump, cost):\n",
    "                if length < j:\n",
    "                    ans = min(ans, inc + c + dec * (j - length))\n",
    "                    continue\n",
    "                q, r = divmod(length, j)\n",
    "                if r == 0:\n",
    "                    ans = min(ans, c + dfs(q))\n",
    "                else:\n",
    "                    ans = min(ans, c + r * inc + dfs(q), c + (j - r) * dec + dfs(q + 1))\n",
    "            return ans\n",
    "\n",
    "        return dfs(target) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(x) -> int:\n",
    "            if x == 0:\n",
    "                return 0\n",
    "            if x == 1:\n",
    "                return inc\n",
    "            res = x * inc\n",
    "            for i,jmp in enumerate(jump):\n",
    "                res = min(res,inc * (x % jmp) + cost[i] + dfs(x // jmp))\n",
    "                if x % jmp != 0:\n",
    "                    res = min(res,dec * (jmp - x % jmp) + cost[i] + dfs(x // jmp + 1))\n",
    "            return res\n",
    "        return dfs(target) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def search(num):\n",
    "            if num == 0:\n",
    "                return 0\n",
    "            result = num * inc\n",
    "            for i in range(len(jump)):\n",
    "                last, left = num // jump[i], num % jump[i]\n",
    "                result = min(result, search(last) + cost[i] + inc * left)\n",
    "                if num > 1 and left > 0:\n",
    "                    result = min(result, search(last + 1) + cost[i] + dec * (jump[i] - left))\n",
    "            return result\n",
    "\n",
    "        return search(target) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7;\n",
    "        @cache\n",
    "        def f(target):\n",
    "            print(target)\n",
    "            if target == 0:\n",
    "                return 0\n",
    "            if target == 1:\n",
    "                return inc\n",
    "            res = target * inc\n",
    "            for i in range(len(jump)):\n",
    "                x = target % jump[i]\n",
    "                res = min(res, x * inc + cost[i] + f(target // jump[i]))\n",
    "                if x != 0:\n",
    "                    res = min(res, (jump[i] - x) * dec + cost[i] + f(target // jump[i] + 1))\n",
    "            return res\n",
    "        return f(target) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        @cache\n",
    "        def min_cost(t):\n",
    "            if t == 1: return inc\n",
    "            ans = (t) * inc\n",
    "            for j, c in zip(jump, cost):\n",
    "                nxt = t // j\n",
    "                if 0 < nxt < t:\n",
    "                    ans = min(ans, c + abs(nxt * j - t) * inc + min_cost(nxt))\n",
    "                if nxt + 1 < t:\n",
    "                    ans = min(ans, c + abs(nxt * j + j - t) * dec + min_cost(nxt+1))\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        return min_cost(target) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        pq, d = [(0,target)], {}\n",
    "        while pq:\n",
    "            w,u = heappop(pq)\n",
    "            if u==0:\n",
    "                return w%mod\n",
    "            if u in d:\n",
    "                continue\n",
    "            d[u] = w\n",
    "            heappush(pq, (w+u*inc,0))\n",
    "            for k,w2 in zip(jump,cost):\n",
    "                q,r = divmod(u,k)\n",
    "                heappush(pq,(w+r*inc+w2,q))\n",
    "                heappush(pq,(w+(k-r)*dec+w2,q+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param target:\n",
    "        :param inc:\n",
    "        :param dec:\n",
    "        :param jump:\n",
    "        :param cost:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        sd1 = SortedList(key=lambda x:x[1])\n",
    "        touched = {}\n",
    "        sd1.add((target, 0))\n",
    "\n",
    "        while sd1:\n",
    "            cur, cost1 = sd1.pop(0)\n",
    "            if cur == 0:\n",
    "                return cost1 % (10**9+7)\n",
    "            if cur not in touched:\n",
    "              touched[cur] = cost1\n",
    "            else:\n",
    "              if touched[cur] <= cost1:\n",
    "                continue\n",
    "              touched[cur] = cost1\n",
    "            sd1.add((0, cost1 + inc * cur))\n",
    "            for i in zip(jump, cost):\n",
    "                left = cur % i[0]\n",
    "                sd1.add((cur//i[0], cost1 + left * inc + i[1]))\n",
    "                sd1.add((cur // (i[0]) + 1, cost1 + (i[0]-left) * dec + i[1]))\n",
    "        return -1\n",
    "\n",
    "a = Solution()\n",
    "print(a.busRapidTransit(target = 995000, inc = 2, dec = 1, jump = [1000000], cost = [99]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        self.num = len(jump)\n",
    "        self.cost = cost \n",
    "        self.jump = jump \n",
    "        self.inc = inc \n",
    "        self.dec = dec\n",
    "        return self.dfs(target)%1000000007 \n",
    "    @lru_cache(None)\n",
    "    def dfs(self,target):\n",
    "        if target == 0:\n",
    "            return 0\n",
    "        if target == 1:\n",
    "            return self.inc \n",
    "        res = target * self.inc \n",
    "        for i in range(self.num):\n",
    "            vehicle = self.jump[i]\n",
    "            if target%self.jump[i] == 0:\n",
    "                res = min(res,self.dfs(target//vehicle) + self.cost[i])\n",
    "            else:\n",
    "                res = min(res,self.dfs(target//vehicle) + self.cost[i] + self.inc * (target%vehicle),self.dfs(target//vehicle + 1) + self.cost[i] + self.dec * (vehicle - target%vehicle) )\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        @functools.lru_cache(maxsize=100000)\n",
    "        def dfs(pos):\n",
    "            if pos == 0:\n",
    "                return 0\n",
    "            ans = inc*pos\n",
    "            for i in range(len(jump)):\n",
    "                if pos >1:\n",
    "                    pre = pos//jump[i]\n",
    "                    yu = pos%jump[i]\n",
    "                    if yu == 0:\n",
    "                        ans = min(ans,dfs(pre)+cost[i])\n",
    "                    else:\n",
    "                        ans = min(ans,cost[i]+dfs(pre+1)+dec*(jump[i]-yu),cost[i]+dfs(pre)+inc*yu)\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dfs(target)%int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        @functools.lru_cache(maxsize=100000)\n",
    "        def dfs(pos):\n",
    "            if pos == 0:\n",
    "                return 0\n",
    "            ans = inc*pos\n",
    "            for i in range(len(jump)):\n",
    "                if pos >1:\n",
    "                    pre = pos//jump[i]\n",
    "                    yu = pos%jump[i]\n",
    "                    if yu == 0:\n",
    "                        ans = min(ans,dfs(pre)+cost[i])\n",
    "                    else:\n",
    "                        ans = min(ans,cost[i]+dfs(pre+1)+dec*(jump[i]-yu),cost[i]+dfs(pre)+inc*yu)\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dfs(target)%int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        # memo = dict() #记忆字典\n",
    "        # def findroute(cur_target):  \n",
    "        #     if cur_target==0:     #当前站点已经是0了返回0代价\n",
    "        #         return 0\n",
    "        #     if cur_target in memo:\n",
    "        #         return memo[cur_target]\n",
    "        #     mincost = cur_target*inc  #最小代价初始化为直接回终点站，我相信这种情况应该存在\n",
    "\n",
    "        #     for i,val in enumerate(jump): #遍历附近的公交站点\n",
    "        #         if cur_target>1:#至少得大于1，不然我自己走了还坐个屁公交\n",
    "        #             if cur_target%val==0: #当前站能够坐公交\n",
    "        #                 mincost =min(mincost,cost[i]+findroute(cur_target//val)) #递归下一站\n",
    "        #             else:\n",
    "        #                 bias = cur_target%val #当前站不能做公交看看需要走几步到达公交站  \n",
    "        #                 if cur_target-bias>0: #往前走几步如果没到终点，就该坐公交，递归下一站\n",
    "        #                     mincost=min(mincost,bias*inc+cost[i]+findroute(cur_target//val))\n",
    "\n",
    "        #                 mincost = min(mincost,(val-bias)*dec+cost[i]+findroute(cur_target//val+1))#往后走几步坐公交递归下一站\n",
    "        #     memo[cur_target]=mincost\n",
    "        #     return mincost\n",
    "\n",
    "        # return findroute(target)%(1000000007)\n",
    "        deq = [[0, target]]#最小堆\n",
    "        while deq:\n",
    "            i, t = heapq.heappop(deq)\n",
    "            if t == 0:\n",
    "                return i % (10 ** 9 + 7)\n",
    "            heapq.heappush(deq, [i + t * inc, 0])#直接走到起点\n",
    "            for j, n in enumerate(jump):\n",
    "                mod = t % n\n",
    "                heapq.heappush(deq, [i + mod * inc + cost[j], t // n])#向前走\n",
    "                heapq.heappush(deq, [i + (n - mod) * dec + cost[j], t // n + 1]) #向后走\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:\n",
    "        deq = [[0, target]]#最小堆\n",
    "        while deq:\n",
    "            i, t = heapq.heappop(deq)\n",
    "            if t == 0:\n",
    "                return i % (10 ** 9 + 7)\n",
    "            heapq.heappush(deq, [i + t * inc, 0])#直接走到起点\n",
    "            for j, n in enumerate(jump):\n",
    "                mod = t % n\n",
    "                heapq.heappush(deq, [i + mod * inc + cost[j], t // n])#向前走\n",
    "                heapq.heappush(deq, [i + (n - mod) * dec + cost[j], t // n + 1])#向后走\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
